package com.jinan.algorithm.LinkList;

import com.jinan.common.ListNode;
import com.jinan.common.TreeNode;

import java.math.BigInteger;
import java.util.HashMap;
import java.util.Map;

import static com.jinan.algorithm.LinkList.ReverseList.reverseList;

/**
 * 环形链表
 * 给定一个链表，判断链表中是否有环 如果链表中有某个节点,可以通过连续跟踪next 指针再次到达该节点，则链表中存在环
 * 如果链表中存在环，则返回true 否则，返回false 。
 */
public class CycleList {
    public static void main(String[] args) {
        ListNode node5 = new ListNode(5, null);
        ListNode node4 = new ListNode(4, node5);
        ListNode node3 = new ListNode(3, node4);
        ListNode node2 = new ListNode(2, node3);
        ListNode node1 = new ListNode(1, node2);
//        node5.next = node1;
        System.out.println(ishasCycle(node1));
    }

    /**
     * 判断链表中是否有环
     * 使用快慢指针（Floyd's Cycle-Finding Algorithm）。
     * 快指针每次移动两步，慢指针每次移动一步。如果链表中存在环，那么快指针最终会追上慢指针；
     * 如果链表中不存在环，那么快指针会到达链表的尾部。
     *
     * @param head
     * @return
     */
    public static boolean ishasCycle(ListNode head) {
        if (head == null | head.next == null) {
            return false;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while (slow != fast) {
            if (fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }

    /**
     * 876. 链表的中间结点 <a href="https://leetcode.cn/problems/middle-of-the-linked-list/solution/mei-xiang-ming-bai-yi-ge-shi-pin-jiang-t-wzwm/">...</a>
     * 难度： 简单
     * tag: 链表 快慢指针
     * description:
     * 给定一个头结点为 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
     *
     * @param head 链表头结点
     * @return ListNode 中间结点
     */
    public ListNode middleNode(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    /**
     * 141. 环形链表 <a href="https://leetcode.cn/problems/linked-list-cycle/solution/huan-xing-lian-biao-by-leetcode-solution/">...</a>
     * 难度： 简单
     * tag: 链表 快慢指针
     * description:
     * 给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
     *
     * @param head 链表头结点
     * @return boolean 是否有环
     */
    public boolean hasCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }

    /**
     * 142. 环形链表 II <a href="https://leetcode.cn/problems/linked-list-cycle-ii/solution/huan-xing-lian-biao-ii-by-leetcode-solution/">...</a>
     * 难度： 中等
     * tag: 链表 快慢指针
     * description:
     * 给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
     * tips:
     * 假如有环，当slow和fast相遇时，慢指针没有走完一圈，
     * 设head到入环的起点距离为a，环起点到顺时针slow和fast相遇点的距离为b，环起点到逆时针slow和fast相遇点的距离为c，
     * 则slow指针走过的距离为a+b，fast指针走过的距离为a+b+n(b+c)，其中n为环的圈数，b+c为环的长度。
     * 由fast和slow的公式可以得到，a+b+n(b+c) = 2(a+b)，所以a = (n-1)(b+c) + c。
     * 所以我们可以定义两个指针，一个从head出发，一个从相遇点出发，两个指针每次都只走一个节点，当两个指针相遇时，则该点为入环的第一个节点。
     *
     * @param head 链表头结点
     * @return ListNode 链表开始入环的第一个节点
     */
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                ListNode index1 = head;
                ListNode index2 = slow;
                while (index1 != index2) {
                    index1 = index1.next;
                    index2 = index2.next;
                }
                return index1;
            }
        }
        return null;
    }

    /**
     * 143. 重排链表 <a href="https://leetcode.cn/problems/reorder-list/solution/zhong-pai-lian-biao-by-leetcode-solution/">...</a>
     * 难度： 中等
     * tag: 链表 递归
     * description:
     * 给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
     * 将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
     * 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
     *
     * @param head 链表头结点
     * @return void 无返回值
     * tips:
     * 1. 找到链表的中点，将中点之后的链表反转。
     * 2. 将中点之后的链表插入到中点之前。
     * 3. 将链表拆分成两个链表。
     * 4. 将两个链表合并。
     */
    public void reorderList(ListNode head) {
        ListNode mid = middleNode(head);
        ListNode head2 = reverseList(mid);
        while (head2.next != null) {
            ListNode next = head.next;
            ListNode next2 = head2.next;
            head.next = head2;
            head2.next = next;
            head = next;
            head2 = next2;
        }
    }

    /**
     * 21. 合并两个有序链表 <a href="https://leetcode.cn/problems/merge-two-sorted-lists/solution/he-bing-liang-ge-you-xu-lian-biao-by-leetcode-solutio/">...</a>
     * 难度： 简单
     * tag: 链表
     * description:
     * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
     * restriction:
     * 1. 两个链表的节点数目范围是 [0, 50]
     * 2. -100 <= Node.val <= 100
     * tips:
     * 1. 递归
     * 2. 迭代
     *
     * @param list1 链表1
     * @param list2 链表2
     * @return ListNode 合并后的链表
     * @apiNote 思路：
     * 1. 递归：
     * 2. 迭代：
     */
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode head = new ListNode();
        ListNode cur = head;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                cur.next = list1;
                list1 = list1.next;
            } else {
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }
        cur.next = list1 != null ? list1 : list2;
        return head.next;
    }

    /**
     * 23. 合并K个升序链表 <a href="https://leetcode.cn/problems/merge-k-sorted-lists/solution/he-bing-kge-pa-you-xu-lian-biao-by-leetcode-solutio/">...</a>
     * 难度： 困难
     * tag: 链表 堆 递归
     * description:
     * 给你一个链表数组，每个链表都已经按升序排列。
     * 请你将所有链表合并到一个升序链表中，返回合并后的链
     * restriction:
     * 1. k == lists.length
     * 2. 0 <= k <= 10^4
     * 3. 0 <= lists[i]ListNode.val <= 10^4
     *
     * @param lists 链表数组
     * @return ListNode 合并后的链表
     * @apiNote 思路：
     */
    //暴力
//    public ListNode mergeKLists(ListNode[] lists) {
//        int n = lists.length;
//        ListNode head=null;
//        for (ListNode list : lists) {
//            head = mergeTwoLists(head, list);
//        }
//        return head;
//    }
    // 分治
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        }
        return merge(lists, 0, lists.length - 1);
    }

    public ListNode merge(ListNode[] lists, int left, int right) {
        if (left == right) {
            return lists[left];
        }
        if (left > right) {
            return null;
        }
        int mid = (left + right) >>> 1;
        return mergeTwoLists(merge(lists, left, mid), merge(lists, mid + 1, right));
    }

    /**
     * 160. 相交链表 <a href="https://leetcode.cn/problems/intersection-of-two-linked-lists/solution/xiang-jiao-lian-biao-by-leetcode-solution/">...</a>
     * 难度： 简单
     * tag: 链表 双指针
     * description:
     * 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
     *
     * @param headA 链表1
     * @param headB 链表2
     * @return ListNode 相交的起始节点
     * @apiNote 思路：1.哈希表，2.双指针，A和B都遍历一遍A、B链表，如果遇到相同节点，则返回该节点。
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 哈希
//        Map<ListNode,Integer> map=new HashMap<>();
//        ListNode p=headA;
//        while(p!=null){
//            map.merge(p,1,Integer::sum);
//            p=p.next;
//        }
//        p=headB;
//        while(p!=null){
//            map.merge(p,1,Integer::sum);
//            if(map.get(p)>1){
//                return p;
//            }
//            p=p.next;
//        }
//        return null;
        // 双指针
        if (headA == null || headB == null)
            return null;
        ListNode pA = headA;
        ListNode pB = headB;
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }

    /**
     * 148. 排序链表 <a href="https://leetcode.cn/problems/sort-list/solution/pai-xu-lian-biao-by-leetcode-solution/">...</a>
     * 难度： 中等
     * tag: 链表 归并排序
     * description:
     * 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
     * restrictions:
     * 链表中节点的数目在范围 [0, 5 * 10^4] 内
     * -10^5 <= Node.val <= 10^5
     *
     * @param head 链表头结点
     * @return ListNode 排序后的链表头结点
     * @apiNote 思路：归并排序
     */
    public ListNode sortList(ListNode head) {
        // 边界条件：如果链表为空或只有一个结点，直接返回该结点
        if (head == null || head.next == null) {
            return head;
        }
        // 快慢指针找到链表的中点
        ListNode dummy = new ListNode(-1, head);
        ListNode fast = dummy, slow = dummy;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode right = sortList(slow.next);
        slow.next = null;
        ListNode left = sortList(head);

        ListNode cur = dummy;
        while (left != null && right != null) {
            if (left.val < right.val) {
                cur.next = left;
                left = left.next;
            } else {
                cur.next = right;
                right = right.next;
            }
            cur = cur.next;
        }
        cur.next = left != null ? left : right;
        return dummy.next;
    }

    public static String minAddToPalindrome(String num) {
        BigInteger original = new BigInteger(num);
        BigInteger k = BigInteger.ZERO;

        while (true) {
            BigInteger candidate = original.add(k);
            if (isPalindrome(candidate.toString())) {
                return k.toString(); // 返回最小加数
            }
            k = k.add(BigInteger.ONE); // 增加加数
        }
    }

    private static boolean isPalindrome(String str) {
        int left = 0;
        int right = str.length() - 1;
        while (left < right) {
            if (str.charAt(left) != str.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    /**
     * 61. 旋转链表 <a href="https://leetcode.cn/problems/rotate-list/solution/xuan-zhuan-lian-biao-by-leetcode-solution/">...</a>
     * 难度： 简单
     * tag: 链表
     * description:
     * 给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
     * restrictions:
     * 链表中节点的数目在范围 [0, 500] 内
     * -100 <= Node.val <= 100
     * 0 <= k <= 2 * 10^9
     *
     * @param head 链表头结点
     * @param k    移动位置
     * @return ListNode 旋转后的链表头结点
     */
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null || k == 0) return head;
        int len = 1;
        ListNode pre = head;
        ListNode cur = head;
        ListNode tail = head;
        while (tail.next != null) {
            tail = tail.next;
            len++;
        }
        k = k % len;
        for (int i = 0; i < k; i++) {
            cur = cur.next;
        }
        while (cur.next != null) {
            pre = pre.next;
            cur = cur.next;
        }
        cur.next = head;
        head = pre.next;
        pre.next = null;
        return head;
    }

    /**
     * 86. 分隔链表 <a href="https://leetcode.cn/problems/partition-list/solution/fen-ge-lian-biao-by-leetcode-solution/">...</a>
     * 难度： 简单
     * tag: 链表 双指针
     * description:
     * 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
     * 你应当 保留 两个分区中每个节点的初始相对位置。
     * restrictions:
     * 链表中节点的数目在范围 [0, 200] 内
     * -100 <= Node.val <= 100
     * -200 <= x <= 200
     * @param head 链表头结点
     * @param x 分隔位置
     * @return ListNode 分隔后的链表头结点
     * @apiNote 思路：双指针
     * 1. 创建两个虚拟节点，分别指向小于x和大于等于x的链表头结点
     * 2. 遍历链表，将节点按照小于x和大于等于x的链表进行连接
     * 3. 返回小于x的链表头结点
     */
    public ListNode partition(ListNode head, int x) {
        ListNode dummy1 = new ListNode(-1);
        ListNode dummy2 = new ListNode(-1);
        ListNode p1 = dummy1, p2 = dummy2;
        while(head != null){
            if (head.val < x){
                p1.next = head;
            }else {
                p2.next = head;
            }
            p1 = p1.next;
            p2 = p2.next;
            head = head.next;
        }
        p1.next = dummy2.next;
        p2.next = null;
        return dummy1.next;
    }

    /**
     * 109. 有序链表转换二叉搜索树 <a href="https://leetcode.cn/problems/convert-sorted-list-to-binary-search-tree/solution/you-xu-lian-biao-zhuan-huan-er-cha-sou-suo-shu-by/">...</a>
     * 难度： 中等
     * tag: 链表 二叉搜索树
     * description:
     * 给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
     * 本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
     * restrictions:
     * -2^31 <= Node.val <= 2^31 - 1
     * @param head 链表头结点
     * @return TreeNode 二叉搜索树的头结点
     * @apiNote 思路：
     * 1. 找到链表中点，作为二叉搜索树的根节点
     * 2. 递归构建左子树和右子树
     * 3. 返回二叉搜索树的头结点
     */
    public TreeNode<Integer> sortedListToBST(ListNode head) {
        if(head == null){
            return null;
        }else if(head.next == null){
            return new TreeNode<>(head.val);
        }

        ListNode mid = middleNode(head);
        ListNode premid = head;
        while(premid.next != mid){
            premid = premid.next;
        }
        premid.next = null;
        ListNode right = mid.next;
        mid.next = null;
        TreeNode<Integer> root = new TreeNode<>(mid.val);
        root.left = sortedListToBST(head);
        root.right = sortedListToBST(right);
        return root;
    }


}
